package solution

import (
	"fmt"
	"myleecode/solution/common"
	"strings"
)

// 91. 解码方法
// 解法：动态规划
func Leecode91_numDecodings(s string) int {
	if s[0] == '0' {
		return 0
	}
	size := len(s)
	curr, pre := 1, 1
	for i:=1; i<size; i++ {
		tmp := curr
		if s[i] == '0' {
			if s[i-1] == '1' || s[i-1] == '2' {
				curr = pre
			} else {
				return 0
			}
		} else if s[i-1] == '1' || s[i-1] == '2' && s[i] >= '1' && s[i] <= '6' {
			curr = curr + pre
		}
		pre = tmp
	}
	return curr
}

// 92. 反转链表
//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
//链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]

func Leecode92_reverseBetween(head *common.ListNode, left int, right int) *common.ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}
	if left > right {
		return head
	}
	p := head
	var ln, rn *common.ListNode
	for p != nil {
		left--
		right--
		if left == 1 {
			ln = p
		}
		if right == 1 {
			rn = p
			break
		}

		p = p.Next
	}
	if ln == nil {
		if rn != nil {
			ln = rn
			rn = rn.Next
			ln.Next = rn.Next
			rn.Next = ln
			return rn
		}
		return rn
	}
	fmt.Println(ln.Val, rn.Val)
	//tmp := rn.Next
	ln.Next = rn.Next
	rn.Next = ln.Next.Next
	ln.Next.Next = rn
	return head
}

// 93. 复原IP地址
func Leecode93_restoreIpAddresses(s string) []string {
	size := len(s)
	var result []string
	var dfs func(split, begin int)
	isIPSegment := func(from, end int) bool {
		length := from - end + 1
		if length > 1 && s[from] == '0' {
			return false
		}
		ipSeg := 0
		for from <= end {
			ipSeg = ipSeg*10 + int(s[from] - '0')
			from++
		}
		return ipSeg >=0 && ipSeg <= 255
	}
	var ipAddress []string
	dfs = func(residue, begin int) {
		if begin == size {
			if residue == 0 {
				result = append(result, strings.Join(ipAddress, "."))
			}
			ipAddress = ipAddress[:0]
			return
		}
		for i:=begin; i<begin +3; i++ {
			if i >= size {
				break
			}
			if residue * 3 < size - i {
				continue
			}
			if isIPSegment(begin, i) {
				str := s[begin:i+1]
				ipAddress = append(ipAddress, str)
				dfs(residue-1, i)
				ipAddress = ipAddress[:len(ipAddress)-1]
			}
		}
	}
	dfs(4, 0)
	return result
}

// 94: 二叉树中序遍历
func Leecode94_inorderTraversal(root *common.TreeNode) []int {
	var inOrder func(r *common.TreeNode)
	var result []int
	inOrder = func(r *common.TreeNode) {
		if r != nil {
			inOrder(r.Left)
			result = append(result, r.Val)
			inOrder(r.Right)
		}
	}
	inOrder(root)
	return result
}

// 97: 交错字符串
func Leecode97_isInterleave(s1, s2, s3 string) bool {
	l1,l2,l3 := len(s1), len(s2), len(s3)
	if l1 + l2 != l3 {
		return false
	}
	dp := make([][]bool, l1+1)
	for i:=0; i<l1+1; i++ {
		dp[i] = make([]bool, l2+1)
	}

	for i:=1; i<l1+1; i++ {
		dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
	}
	for j:=1; j<l2+1; j++ {
		dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
	}
	for i:=1; i<l1+1; i++ {
		for j:=1; j<l2+1; j++ {
			dp[i][j] = (dp[i][j-1] && s2[j-1] == s3[i+j-1]) || (dp[i-1][j] && s1[i-1] == s3[i+j-1])
		}
	}
	return dp[l1][l2]
}

// 98: 验证二叉搜索树
// 中序遍历
func Leecode98_isValidBST(root *common.TreeNode) bool {
	var isValidBST func(r *common.TreeNode) bool

	pre := root.Val
	isValidBST = func(r *common.TreeNode) bool {
		if r != nil {
			isValidBST(r.Left)
			if r.Left != nil && r.Left.Val > r.Val {
				return false
			}
			if r.Right != nil && r.Right.Val < r.Val {
				return false
			}
			isValidBST(r.Right)
		}
		_ = pre
		return true
	}

	return isValidBST(root)
}